#include <exception>
#include <memory>
#include <functional>
#include <algorithm>
#include <array>
#include <vector>
#include <climits>

class Overlap : public std::exception { };

struct Node
{
	int m_bottom, m_up, m_left, m_right, m_xmid, m_ymid;
	bool m_full;
	std::array<std::unique_ptr<Node>,4> m_children;
	Node(int left = 0, int bottom = 0, int right = 0, int up = 0)
	{
		m_left = left;
		m_bottom = bottom;
		m_right = right;
		m_up = up;
		m_xmid = (m_left + m_right) / 2;
		m_ymid = (m_bottom + m_up) / 2;
		m_full = m_bottom == m_up && m_left == m_right;
		if (m_left + 1 == m_right) {
			m_children[0] = std::unique_ptr<Node>(new Node());
			m_children[2] = std::unique_ptr<Node>(new Node());
		}
		if (m_bottom + 1 == m_up) {
			m_children[0] = std::unique_ptr<Node>(new Node());
			m_children[1] = std::unique_ptr<Node>(new Node());
		}
	}
	void add(int left, int bottom, int right, int up)
	{
		if (m_full) throw Overlap();
		if (m_left == left && 
			m_bottom == bottom && 
			m_right == right && 
			m_up == up &&
			std::all_of(m_children.cbegin(), m_children.cend(), [](const std::unique_ptr<Node>& child) { 
			return !child || (child->m_left == child->m_right && child->m_bottom == child->m_up);
		}))
		{
			m_full = true;
			return;
		}
		if (bottom < m_ymid) {
			if (left < m_xmid) {
				if (!m_children[0]) m_children[0] = std::unique_ptr<Node>(new Node(m_left, m_bottom, m_xmid, m_ymid));
				m_children[0]->add(left, bottom, std::min(right, m_xmid), std::min(up, m_ymid));
			}
			if (right > m_xmid) {
				if (!m_children[1]) m_children[1] = std::unique_ptr<Node>(new Node(m_xmid, m_bottom, m_right, m_ymid));
				m_children[1]->add(std::max(left, m_xmid), bottom, right, std::min(up, m_ymid));
			}
		}
		if (up > m_ymid) {
			if (left < m_xmid) {
				if (!m_children[2]) m_children[2] = std::unique_ptr<Node>(new Node(m_left, m_ymid, m_xmid, m_up));
				m_children[2]->add(left, std::max(m_ymid, bottom), std::min(m_xmid, right), up);
			}
			if (right > m_xmid) {
				if (!m_children[3]) m_children[3] = std::unique_ptr<Node>(new Node(m_xmid, m_ymid, m_right, m_up));
				m_children[3]->add(std::max(m_xmid, left), std::max(m_ymid, bottom), right, up);
			}

		}
		m_full = std::all_of(m_children.cbegin(), m_children.cend(), [](const std::unique_ptr<Node>& child) { return child && child->m_full; });
	}
};

class Solution
{
public:
	bool isRectangleCover(std::vector<std::vector<int>>& rectangles)
	{
		auto bottom = std::numeric_limits<int>::max(),
			up = std::numeric_limits<int>::min(),
			left = std::numeric_limits<int>::max(),
			right = std::numeric_limits<int>::min();
		for (const auto& rect : rectangles) {
			left = std::min(left, rect[0]);
			bottom = std::min(bottom, rect[1]);
			right = std::max(right, rect[2]);
			up = std::max(up, rect[3]);
		}
		auto root = std::unique_ptr<Node>( new Node(left, bottom, right, up));
		for (const auto& rect : rectangles) {
			try {
				root->add(rect[0], rect[1], rect[2], rect[3]);
			} catch (const Overlap& e) {
				return false;
			}
		}
		return root->m_full;
	}
};